package com.salim.leetcode.$6;

/**
 * Created with IntelliJ IDEA.
 * User: clevo
 * Date: 15-9-11
 * Time: 下午3:12
 * To change this template use File | Settings | File Templates.
 */
public class ZigZagConversionVer2 {
    public String convert(String s, int numRows) {
        if(s.length() == 0){
            return s;
        }
        if(s.length()<=numRows){
            return s;
        }
        if(numRows==1){
            return s;
        }
        StringBuffer result = new StringBuffer();
        int singleColNumCount = numRows;
        int zigzagColNumCount = numRows - 2 >=0?numRows-2:0;
        int sector = singleColNumCount + zigzagColNumCount;
        int numColsA = (s.length()/sector)*(1+zigzagColNumCount);
        int numColsB = s.length()%sector;
        int numColsC = 0;
        int numCols = 0;
        //基准为 14/4 A=6 B=4
        if(numColsB>=singleColNumCount){
            numColsC++;
            numColsB=numColsB-singleColNumCount;
            for(int i=0;i<numColsB;i++){
                numColsC++;
            }
        }else{
            numColsC = numColsB==0?0:1;
        }

        //总列数
        numCols = numColsA + numColsC;

        int[][] arrays = new int[numRows][numCols];

        boolean inZigZag = false;
        int rowIndex = 0;
        int colIndex = 0;

        for(int i=0;i<s.length();i++){

            arrays[rowIndex][colIndex] = i;
            //竖列
            if(!inZigZag){
                if(rowIndex<singleColNumCount-1){
                    rowIndex++;
                    continue;
                }else{
                    inZigZag = true;
                    colIndex++;
                    rowIndex--;
                    continue;
                }
            }
            //斜列
            if(inZigZag){
                if(rowIndex!=0){
                    colIndex++;
                    rowIndex--;
                    continue;
                }else{
                    inZigZag = false;
                    rowIndex++;
                    continue;
                }
            }
        }

        //result.append(s.charAt(0));
        int linelengthleft = 0;
        int linelengthright = 0;
        int lineindex = 0;
        boolean inSingleCol = true;
        for(int i=0;i<numRows-1;i++){
            inSingleCol = true;
            linelengthleft = zigzagColNumCount + 1 - i;
            linelengthright = i;
            lineindex=0;
            while (lineindex<numCols){
                result.append(s.charAt(arrays[i][lineindex]));
                if(inSingleCol||i==0){
                    lineindex+=linelengthleft;
                    inSingleCol = false;
                }else{
                    lineindex+=linelengthright;
                    inSingleCol = true;
                }
            }
/*
            for(lineindex=0;lineindex<numCols;lineindex+=linelengthleft){
                result.append(s.charAt(arrays[i][lineindex]));
            }*/
            if(lineindex>=numCols){
                if(inSingleCol){
                    lineindex-=linelengthright;
                }else{
                    lineindex-=linelengthleft;
                }
            }
            if(arrays[i][lineindex]==0&&i!=0){
                result.deleteCharAt(result.length()-1);
            }
        }
        linelengthleft = zigzagColNumCount + 1 ;
        for(lineindex=0;lineindex<numCols;lineindex+=linelengthleft){
            result.append(s.charAt(arrays[numRows-1][lineindex]));
        }
        if(lineindex>=numCols){
            lineindex-=linelengthleft;
        }
        if(arrays[numRows-1][lineindex]==0){
            result.deleteCharAt(result.length()-1);
        }
        return result.toString();
    }

    public static void main(String[] args){
        ZigZagConversionVer2 temp = new ZigZagConversionVer2();
/*        String s ="PAYPALISHIRING";
        int row = 3;
        System.out.println(temp.convert(s,row));
        String a = "ABC";
        System.out.println(temp.convert(a,2));
        String a1 = "AB";
        System.out.println(temp.convert(a1,1));
        String abcde = "ABCDE";
        System.out.println(temp.convert(abcde,3));
        String abcde4 = "ABCDE";
        System.out.println(temp.convert(abcde4,4));*/
        String abcd ="ABCD";
        System.out.println(temp.convert(abcd,2));
/*        String PAYPALISHIRING = "PAYPALISHIRING";
        System.out.println(temp.convert(PAYPALISHIRING,4));*/
    }
}
